[AGC002E]Candy Piles

2020-02-13
#idea #博弈论 #杨氏图
Atcoder

题意

有$n$堆糖果$\{a_i\}$，每次可以吃掉一颗或者把最多的一堆吃完，问先手的胜负

题解

把糖果排列成这样：

1
2
3
4
5
100000000000
111000000000
001100000
0001
000

行动被描述为一条折线，往下是吃完一堆，往右是吃一颗

然后会发现左上-右下对角线上胜负态相同

找到对角线上离边界最近的，若与其中一条边界相距距离为奇数则必胜

调试记录

无

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <cstdio>
#include <algorithm>
const int maxn = 1e5 + 5;
using namespace std;
int a[maxn], n;
bool cmp(const int &x, const int &y){
	return x > y;
}
int main(){
	scanf("%d", &n);
	for (int i = 1; i <= n; i++) scanf("%d", a + i);
	sort(a + 1, a + n + 1, cmp);
	for (int i = 1; i <= n; i++){
		if (i + 1 > a[i + 1]){
			int ans = 0, j = i;
			while (a[j + 1] == i) ++j;
			ans = ((a[i] - i) & 1) | ((j - i) & 1); 
			if (ans) puts("First");
			else puts("Second");
			return 0;
		}
	}
	return 0;
}